#include <stdio.h>
#include <stdlib.h>


#include "SqList.h"


/**
 * 
 * 算法2.3
 * 
 * 构造一个空的线性表
*/
Status InitList(SqList *L)
{
    ElemType *temp;
    temp = malloc(LIST_INIT_SIZE*sizeof(ElemType));
    if (!temp)
    {
        return OVERFLOW;
    }
    
    L->elem = temp;
    L->length = 0;
    L->listsize = LIST_INIT_SIZE;
    return OK;
}

/**
 * 
 * 销毁线性表
*/
Status DestroyList(SqList *L)
{
    if (L == NULL || L->elem == NULL)
    {
        return ERROR;
    }

    free(L->elem);

    L->elem = NULL;
    L->length = 0;
    L->listsize = 0;

    return OK;
}

/**
 * 
 * 将L置为空表
*/
Status ClearList(SqList *L)
{
    if (L == NULL || L->elem == NULL)
    {
        return ERROR;
    }
    
    L->length = 0;
    return OK;
}


/**
 * 
 * 若L为空表，则返回TRUE，否则返回FALSE
*/
Boolean ListEmpty(SqList *L)
{
    return L->length==0 ? TRUE :FALSE;
}


/**
 * 返回线性表中元素个数
*/
int ListLength(SqList L)
{
   return L.length;
}


/**
 * 用ElemType返回线性表中第i个元素的值
*/
Status GetElem(SqList L,int i,ElemType *e)
{
    if (i<0 || i>L.length-1)
    {
        return ERROR;
    }

    *e = L.elem[i];
    return OK;
}


/**
 * 返回线性表中第1一个与出入ElemType满足关系compare_op的数据元素的位序。若这样的元素不存在，则返回值为0
*/
int LocateElem(SqList L,ElemType e,compare_op *op)
{
    ElemType *p;
    int i=0;

    p = L.elem;

    while (i<L.length && !op(p++,&e))
        i++;
    
    if (i<L.length)
        return i;
    else
        return -1;
}


/**
 * 若 cur_e是L的数据元，且不是第一个，则用 pre_e返回它的前驱，否则操作失败,pre_e无定义。
*/
Status PriorElem(SqList L,ElemType cur_e,ElemType *pre_e)
{
    int i = 0;

    if (L.elem==NULL || L.length < 2 )
    {
        return ERROR;
    }

    while ((i<L.length) && (L.elem[i] != cur_e))
    {
        ++i;    /* code */
    }
    
    if (i==0 || i>=L.length)
    {
        return ERROR;
    }

    *pre_e = L.elem[i-1];

    return OK;
}



/**
 * 若 cur_e是L的数据元素，且不是最后一个,则用next_e 返回它的后，否则操作失败,next_e无定义。
*/
Status NextElem(SqList L,ElemType cur_e,ElemType *next_e)
{
    int i = 0;
    if (L.elem==NULL || L.length<2)
    {
        return ERROR;
    }
    
    while (i<L.length-1 && L.elem[i]!=cur_e)
    {
        ++i;
    }

    if (i>=L.length-1)
    {
        return ERROR;
    }
    
    *next_e = L.elem[L.length+1];
    
    return OK;
}


/**
 * 算法2.4
 * 
 * 在L中第i个位置之前插入新的数据元素e，L的长度加1
*/
Status ListInsert(SqList *L,int i,ElemType e)
{
    ElemType *temp,*p,*q;
    
    if (i<0 || i>L->length)
    {
        return ERROR;
    }

    if (L->length >= L->listsize)
    {
        temp = realloc(L->elem,(LISTINCREMENT+L->listsize)*sizeof(ElemType));
        if (!temp)
        {
            return OVERFLOW;
        }
        L->elem = temp;
        L->listsize += LISTINCREMENT ;
    }
    
    q = &L->elem[i];

    for ( p = &L->elem[L->length-1]; p >= q; p--)
    {
        *(p+1) = *p;        
    }

    L->elem[i] = e;
    ++L->length;
    return OK;
}


/**
 *  算法2.5
 * 
 * 删除L的第i个数据元素，并用e返回其值，L的长度减1
*/
Status ListDelete(SqList *L,int i,ElemType *e)
{
    ElemType *q;
    if (i<0 || i>L->length-1)
    {
        return ERROR;
    }

    q = &L->elem[i];
    *e = *q;

    for ( ++q;  q <= &L->elem[L->length-1]; q++)
    {
        *(q-1) = *q;
    }
    --L->length; 

    return OK;
}


/**
 * 依次对L的每个数据元素调用函数 visit()，一旦visit()失败，则操作失败
*/
void ListTraverse(SqList L,visit_op *op)
{
    int i;
    
    for ( i = 0; i < L.length; i++)
    {
        op(&L.elem[i]);
    }
    printf("\n");
    return ;
}








